package core;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

import org.apache.commons.lang3.SerializationUtils;

import util.IO;
import util.Parameters;

public class GeneticAlgorithm {
	public static Problem problem;
	public static double bestCost = Double.MAX_VALUE;
	public static Problem bestProblem = null;
	
	
	public static void DoGeneticAlgorithm(String pathFile){
		//construir solução inicial
		problem = IO.Read(pathFile);
		//fazer primeira geração
		ArrayList<Problem> parents = CreateFirstGeneration();
		
		for (int i = 0; i < Parameters.numberIterations; i++) {
			//fazer crossover
			ArrayList<Problem> children = DoCrossOver(parents, i);
			//fazer mutacao
			DoMutation(children);
			//fazer selecao
			//children = DoSelectionBestFitness(parents, children);
			children = DoSelectionTournament(parents, children, (int) Parameters.numberPopulation / 10, (int) Parameters.numberPopulation/20);
			//escolher melhor solucao	
			for (int j = 0; j < children.size(); j++) {
				if(children.get(j).getCost() < bestCost){
					bestProblem = children.get(j);
					bestCost = bestProblem.getCost();
					//System.out.println(bestCost);
				}
			}
			
			//organizar para proxima geração
			parents = children;
			
			//printar
			System.out.println(i+" : "+bestCost+"  [ "+bestProblem.PrintPermutation()+"]");
		}
	}
	
	private static void DoMutation(ArrayList<Problem> pop){
		Random r = new Random();
		int n = pop.get(0).getPermutation().length;
		
		for (int i = 0; i < pop.size(); i++) {
			//fazer mutação
			Problem p = pop.get(i);
			if(r.nextDouble() <= Parameters.mutationPercentage){
				Pair pair = new Pair(r.nextInt(n), r.nextInt(n));
				//mudar permutacao
				p.ChangeDestinationColumn(pair.getFirst(), pair.getSecond());
				p.ChangeDestinationLine(pair.getFirst(), pair.getSecond());
				
				int firstElement = p.getPermutationElement(pair.getFirst());
				int secondElement = p.getPermutationElement(pair.getSecond());
				
				p.setPermutationElement(pair.getFirst(), secondElement);
				p.setPermutationElement(pair.getSecond(), firstElement);
			}
		}
	}
	
	private static ArrayList<Problem> DoSelectionTournament(ArrayList<Problem> parents, 
			ArrayList<Problem> children, int contestantCount, int numVictories){
		ArrayList<Problem> ret = new ArrayList<Problem>();
		ArrayList<Problem> list = new ArrayList<Problem>();
		list.addAll(parents);
		list.addAll(children);
		
		ArrayList<Problem> contestants = new ArrayList<Problem>();
		
		Collections.shuffle(list);
		
		//adicionar competidores aleatoriamente
		for (int i = 0; i < contestantCount; i++) {
			contestants.add(list.get(i));
		}
		
		int victories;
		
		for (Problem p : list) {
			victories = 0;
			for (Problem c : contestants) {
				if(p.getCost() < c.getCost()){
					victories++;
				}
			}
			
			if( (victories >= numVictories) && (ret.size() < parents.size())){
				ret.add(p);
			}
		}
		
		if(ret.size() < parents.size())
			return DoSelectionTournament(parents, children, contestantCount, numVictories-1);
		
		return ret;
	}
	
	private static ArrayList<Problem> DoSelectionBestFitness(ArrayList<Problem> parents, 
			ArrayList<Problem> children) {
		ArrayList<Problem> list = new ArrayList<Problem>();
		
		list.addAll(parents);
		list.addAll(children);

		//ordenar
		Collections.sort(list, new Comparator<Problem>() {
			public int compare(Problem o1, Problem o2) {
				if(o1.getCost() > o2.getCost()){
					return 1;
				}else if(o1.getCost() < o2.getCost()){
					return -1;
				}else{
					return 0;
				}
			}
			
		});
		
		int half = list.size()/2;
		
		//remover os piores elementos
		for (int i = half; i < half*2; i++) {
			list.remove(half);
		}
		
		return list;
	}
	
	private static ArrayList<Problem> DoCrossOver(ArrayList<Problem> parents, int gen){
		int tam = parents.size();
		int half = tam/2;
		
		//int pivot = (int) parents.get(0).getPermutation().length / 2; //pivot fixo pela metade
		//int pivot = new Random().nextInt(parents.get(0).getPermutation().length); //pivot variável
		int pivot = new Random().nextInt(3) - 1 + (int) parents.get(0).getPermutation().length / 2; //pivot variável com min e max
		
				
		Problem[] parents1 = new Problem[tam/2];
		Problem[] parents2 = new Problem[tam/2];
		Problem[] children = new Problem[Parameters.numberPopulation];
		
		//preenchendo arrays
		for (int i = 0, j = tam/2; i < tam/2; i++, j++) {
			parents1[i] = parents.get(i);
			parents2[i] = parents.get(j);
		}
		
		//fazer crossover - filho 1
		for (int i = 0; i < half; i++) {
			children[i] = new Problem();
			children[i].setGeneration(gen);
			children[i].setPermutation(mixVector(parents1[i].getPermutation(), parents2[i].getPermutation(), pivot));
			children[i] = Do2Troca(children[i]);
			children[i].setCost(EvaluateSolution(children[i]));
		}
		
		//fazer crossover - filho 2
		for (int i = half, j =0 ; i < tam; i++, j++) {
			children[i] = new Problem();
			children[i].setGeneration(gen);
			children[i].setPermutation(mixVector(parents2[j].getPermutation(), parents1[j].getPermutation(), pivot));
			children[i] = Do2Troca(children[i]);
			children[i].setCost(EvaluateSolution(children[i]));
		}
		
		//desordenar
		ArrayList<Problem> ret = new ArrayList<Problem>(Arrays.asList(children));
		Collections.shuffle(ret, new Random());
		
		return ret;
	}
	
	private static ArrayList<Problem> CreateFirstGeneration(){
		ArrayList<Problem> list = new ArrayList<Problem>();
		Random r = new Random();
		int populationCount = Parameters.numberPopulation;
		
		int permutationSize = problem.getSize();
		
		//criar cada membro da população
		for (int i = 0; i < populationCount; i++) {
			Problem s = new Problem();
			//gerar permutação
			s.setPermutation(GeneratePermutation(permutationSize));
			//fazer as trocas
			s = Do2Troca(s);
			s.setCost(EvaluateSolution(s));
			
			list.add(s);
		}
		
		return list;
	}
	
	private static double EvaluateSolution(Problem p){
		int tam = p.getFlux().length;

		double temp = 0;
		for (int i = 0; i < tam; i++) {
			for (int j = 0; j < tam; j++) {
				if (j > i) {
					// resultado += fluxo (ij) * distancia (pi[i] pi[j])
					// quando j > i
					temp += p.getFlux()[i][j]
							* p.getDestination()[i][j];
				}
			}
		}

		return temp;

	}
	
	private static Problem Do2Troca(Problem s){
		ArrayList<Pair> pairs = new  ArrayList<Pair>();
		Problem temp = SerializationUtils.clone((Problem) problem);
		Problem sol = SerializationUtils.clone((Problem) s);
		
		int[] per = sol.getPermutation();
		
		//receber os pares das permutações
		for (int i = 0; i < per.length; i++) {
			for (int j = 0; j < per.length; j++) {
				if(i == per[j]){
					Pair pair = new Pair(i,j);
					pairs.add(pair);
					break;
				}
			}
		}
		
		Collections.reverse(pairs);
		
		//efetuar troca dos pares na soluçao inicial e permutacao
		for (Pair pair : pairs) {
			temp.ChangeDestinationColumn(pair.getFirst(), pair.getSecond());
			temp.ChangeDestinationLine(pair.getFirst(), pair.getSecond());
			
			int firstElement = temp.getPermutationElement(pair.getFirst());
			int secondElement = temp.getPermutationElement(pair.getSecond());
			
			temp.setPermutationElement(pair.getFirst(), secondElement);
			temp.setPermutationElement(pair.getSecond(), firstElement);
		}
		
		
		return temp;
	}
	
	//Métodos auxiliares
	private static int[] mixVector(int[] v1, int[] v2, int pivot){
		int[] vec = new int[v1.length]; 
		
		for (int i = 0; i < vec.length; i++) {
			if(i < pivot){
				vec[i] = v1[i];
			}else{
				vec[i] = v2[i];
			}
		}
		
		return vec;
	}
	
	private static int[] GeneratePermutation(int permutationSize){
		int[] array = new int[permutationSize];
		
		//criando lista
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < permutationSize; i++) {
			list.add(i);
		}
		//randomizar lista
		Collections.shuffle(list);
		//converter para array
		for (int i = 0; i < permutationSize; i++) {
			array[i] = list.remove(0);
		}
		return array;
	}
}
